package euler.p001_050;

import java.util.Arrays;

import euler.MainEuler;
import euler.helper.NaturalHelper;
import euler.helper.Utils;

public class Euler024 extends MainEuler {

    /*
        A permutation is an ordered arrangement of objects.
        For example, 3124 is one possible permutation of
        the digits 1, 2, 3 and 4.
        If all of the permutations are listed numerically or
        alphabetically, we call it lexicographic order.
        The lexicographic permutations of 0, 1 and 2 are:

        012   021   102   120   201   210

        What is the millionth lexicographic permutation
        of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

     */


	public String resolve(Integer[] digits, int target) {

        int total = 0;
        int pos = 0;

        while ((total < target) && (pos < digits.length)) {

            long f = NaturalHelper.factorial(digits.length-pos-1);

            if (f + total <= target) {

                int j = 0;

                for (int i = 0; i < digits.length - pos + 1; i++) {
                    if (total + f*i > target - 1) {
                        j = i - 1;
                        break;
                    }
                }

                if (j != 0) {
                    int aux = digits[pos];
                    digits[pos] = digits[pos + j];
                    digits[pos + j] = aux;

                    Arrays.sort(digits, pos + 1, digits.length);
                }

                total+=(j*f);
            }

            pos++;
        }

        return Utils.join(digits,"");
    }
}
